#include <iostream>
#include <assert.h>
#include <memory>
#include <utility>
using namespace std;

namespace apex
{
	// 链表结点类
	template <class T>
	struct list_node
	{
		T _data;
		list_node<T> *_next;
		list_node<T> *_prev;

		list_node(const T &val = T())
			: _data(val), _next(nullptr), _prev(nullptr)
		{
			std::cout << "list_node(const T &val)" << std::endl;
		}

		list_node(T &&val)
			: _data(forward<T>(val)), _next(nullptr), _prev(nullptr)
		{
			std::cout << "list_node(T &&val)" << std::endl;
		}
	};

	// 正向迭代器类
	template <class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef list_node<T> Node;

		typedef __list_iterator<T, Ref, Ptr> iterator;

		// 成员属性 _node
		Node *_node;

		// 成员函数

		// 构造函数
		__list_iterator(Node *node)
			: _node(node)
		{
		}

		// 解引用运算符重载
		Ref operator*()
		{
			return _node->_data;
		}
		// 成员访问符重载
		Ptr operator->()
		{
			return &(operator*());
			// return &_node->_data;
		}

		// 前置++
		iterator &operator++() //__list_iterator<T, Ref, Ptr>& operator++() { }
		{
			_node = _node->_next;
			return *this;
		}
		// 后置++
		iterator operator++(int) //__list_iterator<T, Ref, Ptr> operator++(int) { }
		{
			iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		// 前置--
		iterator &operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		// 后置--
		iterator operator--(int)
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		// 关系运算符
		bool operator==(const iterator &it)
		{
			return _node == it._node;
		}
		bool operator!=(const iterator &it)
		{
			return _node != it._node;
		}
	};

	// 逆向迭代器类
	template <class Iterator, class Ref, class Ptr>
	struct __reverse_iterator
	{
		Iterator _it;
		typedef __reverse_iterator<Iterator, Ref, Ptr> riterator;

		// 构造函数
		__reverse_iterator(Iterator it)
			: _it(it)
		{
		}

		// 解引用运算符重载
		Ref operator*()
		{
			auto tmp = _it;
			return *--tmp;
		}
		// 成员访问符重载
		Ptr operator->()
		{
			return &(operator*()); // return --_it.operator->();
		}

		// 前置++
		riterator operator++()
		{
			--_it;
			return *this;
		}
		// 后置++
		riterator operator++(int)
		{
			riterator tmp(*this);
			--_it;
			return tmp;
		}
		// 前置--
		riterator operator--()
		{
			++_it;
			return *this;
		}
		// 后置--
		riterator operator--(int)
		{
			riterator tmp(*this);
			++_it;
			return tmp;
		}
		// 关系运算符
		bool operator==(const riterator &it)
		{
			return _it == it._it;
		}
		bool operator!=(const riterator &it)
		{
			return _it != it._it;
		}
	};

	// 链表类
	template <class T>
	class list
	{
		// typedef
		typedef list_node<T> Node;

	public:
		typedef __list_iterator<T, T &, T *> iterator;
		typedef __list_iterator<T, const T &, const T *> const_iterator;
		typedef __reverse_iterator<iterator, T &, T *> riterator;
		typedef __reverse_iterator<const_iterator, const T &, const T *> const_riterator;

		// 成员变量
	private:
		Node *_head;
		size_t _size = 0;

	public:
		// head       1     2    3
		// end		begin
		// 迭代器函数
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}
		// 反向迭代器函数
		riterator rbegin()
		{
			return riterator(end());
		}
		riterator rend()
		{
			return riterator(begin());
		}
		const_riterator rbegin() const
		{
			return const_riterator(end());
		}
		const_riterator rend() const
		{
			return const_riterator(begin());
		}

		void swap(list<T> &lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		// 无参构造函数
		list()
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
		}

		// 有参构造函数(初始化n个结点)
		list(size_t n, const T &val = T())
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		// 迭代器构造函数
		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;

			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

		list(initializer_list<T> il)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			for (const auto &e : il)
			{
				push_back(e);
			}
		}
		// 清空链表数据
		void clear()
		{
			/*
			iterator it = begin();
			while (it != end())
			{
				iterator del = it++;
				delete del._node;
			}
			//更新哨兵位
			_head->_next = _head;
			_head->_prev = _head;
			*/

			iterator it = begin();
			while (it != end())
			{
				erase(it++);
			}
		}
		// 析构函数
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		// 拷贝构造
		/*
		list(const list<T>& lt)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;
			for (auto e : lt)
			{
				push_back(e);
			}
		}*/
		// 拷贝构造plus
		list(const list<T> &lt)
		{
			_head = new Node();
			_head->_next = _head;
			_head->_prev = _head;

			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

		// 移动构造
		list(list<T> &&lt)
		{
			swap(lt);
		}

		// 赋值
		/*
		list<T>& operator=(list<T> lt)
		{
			if (this != &lt)
			{
				clear();
				for (auto e : lt)
				{
					push_back(e);
				}
			}
			return *this;
		}
		*/

		// 赋值plus
		list<T> &operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}

		// 移动赋值
		list<T> &operator=(list<T> &&lt)
		{
			swap(lt);
			return *this;
		}

		// 删除pos处数据
		iterator erase(iterator pos)
		{
			assert(pos != end());
			// prv cur/pos next
			Node *cur = pos._node;
			Node *prv = cur->_prev;
			Node *next = cur->_next;

			delete cur;
			// prv连接next
			prv->_next = next;
			next->_prev = prv;

			--_size;
			return iterator(next);
		}

		// pos前插入
		iterator insert(iterator pos, const T &x)
		{
			// prv new cur/pos next
			Node *cur = pos._node;
			Node *prv = cur->_prev;

			Node *newnode = new Node(x);
			// prv连接new
			prv->_next = newnode;
			newnode->_prev = prv;
			// new连接cur
			newnode->_next = cur;
			cur->_prev = newnode;

			++_size;
			return iterator(newnode);
		}

		// 尾插
		void push_back(const T &x)
		{
			/*
			//创建新结点
			Node* newnode = new Node(x);
			//定位尾结点
			Node* tail = _head->_prev;
			//tail连接new
			tail->_next = newnode;
			newnode->_prev = tail;
			//new连接head
			newnode->_next = _head;
			_head->_prev = newnode;
			*/
			std::cout << "void push_back(const T &x)" << std::endl;
			insert(end(), x);
		}

		// 移动插入
		iterator insert(iterator pos, T &&val)
		{
			std::cout << "iterator insert(iterator pos, T &&val)" << std::endl;
			Node *cur = pos._node;
			Node *prev = cur->_prev;

			Node *newnode = new Node(forward<T>(val));
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return iterator(newnode);
		}

		// 移动尾插
		void push_back(T &&val)
		{
			std::cout << "void push_back(T &&val)" << std::endl;
			insert(end(), forward<T>(val));
		}

		// 头插
		void push_front(const T &x)
		{
			insert(begin(), x);
		}

		// 移动头插
		void push_front(T &&val)
		{
			insert(begin(), forward<T>(val));
		}

		// 尾删
		void pop_back()
		{
			erase(--end());
		}

		// 头删
		void pop_front()
		{
			erase(begin());
		}

		size_t size() const
		{
			return _size;
		}
	};
}
